9 函数

发表于   |   分类于   |  

9.1 函数的定义和调用

语法

1
2
3
返回类型 函数名(形式参数){
  函数体
}

简析

组成 说明
返回类型（return type） 每次调用函数返回数据的类型，当不需要返回值时使用void
形式参数（parameter） 每一个参数都必须有类型，没有形参使用void
函数体（body） 用{}括起来的执行部分
实际参数（argument） 为了激活（即调用）函数，需要写出函数名及跟随其后的实际参数列表

9.1.1 程序：计算平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Computes pairwise averages of three numbers
 */
#include <stdio.h>

 float average(float a, float b){
 	return (a+b) / 2;
 }

 int main(){
 	float x, y, z;

 	printf("Enter three numbers:");
 	scanf("%f%f%f", &x, &y, &z);
 	printf("Average of %g and %g: %g\n", x, y, average(x,y));
 	printf("Average of %g and %g: %g\n", y, z, average(y,z));
 	printf("Average of %g and %g: %g\n", x, z, average(x,z));

 	return 0;
 }
1
2
3
4
5
$ ./average
 Enter three numbers:1 2 3
 Average of 1 and 2: 1.5
 Average of 2 and 3: 2.5
 Average of 1 and 3: 2

9.1.2 程序：显示倒数计时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Prints a countdown
 */
#include <stdio.h>
 void print_count(int n){
 	printf("T minus %d and counting\n", n);
 }
 int main(){
 	int i;
 	for(i = 10; i > 0; --i){
 		print_count(i);
 	}
 	return 0;
 }
1
2
3
4
5
6
7
8
9
10
11
./countdwn 
T minus 10 and counting
T minus 9 and counting
T minus 8 and counting
T minus 7 and counting
T minus 6 and counting
T minus 5 and counting
T minus 4 and counting
T minus 3 and counting
T minus 2 and counting
T minus 1 and counting

9.1.3 程序：显示双关语

1
2
3
4
5
6
7
8
9
10
11
/**
 * Prints a bad pun
 */
#include <stdio.h>
 void print_pun(void){
 	printf("To c, or not to c:that is the question.\n");
 }
 int main(){
 	print_pun();
 	return 0;
 }
1
2
$ ./pun2
 To c, or not to c:that is the question.

9.1.4 函数定义

函数定义：

1
2
3
4
返回类型 函数名(形式参数){
  声明
  语句
}

返回值

规则：

  • 函数无法返回数组，但是没有其它关于返回类型的限制
  • 如果忽略返回类型，那么会假定函数返回值的类型是int型
  • 指定返回类型是void型，说明函数没有返回值

技巧：

  • 为每个函数指定一个明显的返回类型是一个很好的方法（void也可以省略，毕竟经典c没有void概念，但不推荐这样）
  • 如果返回值很冗长，比如unsigned long int，那么把返回类型单独放一行是非常有用的

参数列表

规则：

  • 需要在每个形式参数的前面说明其类型
  • 形式参数间用逗号进行分隔
  • 如果函数没有形式参数，那么在()中应该出现void
  • 即使有些形参具有相同数据类型，也必须对每个形式参数分别进行类型说明

函数体

规则：

  • 函数体内声明的变量专属于此函数，其它函数不能对这些变量进行检查或修改
  • 函数体可以为空，以后可以回来编写它的函数体

9.1.5 函数调用

语法：[强制转换返回类型] 函数名(实参1, 实参2 ...);
有无返回值的函数调用的区别：void型的函数调用是语句，所以调用后边始终跟着分号；非void型的函数调用是表达式。
注意：丢掉圆括号仍然是合法的表达式，但不起任何作用，有些编译器会给出警告。

强制转换返回类型

说明：很少用到，可以省略
技巧：可以将返回值强制类型转换成void，使别人清楚编写者使故意扔掉返回值的。

1
(void) printf("Hi, Mom!\n");

9.1.6 程序：判定素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Tests whether a number is prime
 */
#include <stdio.h>
 #define TRUE 1
 #define FALSE 0

 typedef int Bool;
 Bool is_prime(int n){
 	int divisor;

 	if(n <= 1){
 		return FALSE;
 	}
 	for(divisor = 2; divisor * divisor <= n; divisor++){
 		if(n % divisor == 0){
 			return FALSE;
 		}
 	}
 	return TRUE;
 }
 int main(){
 	int n;
 	printf("Enter a number:");
 	scanf("%d", &n);
 	if(is_prime(n)){
 		printf("'Prime'\n");
 	}else{
 		printf("Not prime\n");
 	}
 	return 0;
 }
1
2
3
$ ./prime 
 Enter a number:34
 Not prime

9.2 函数声明

背景：c语言没有要求函数的定义必须放置在main函数的定义之后。如果函数的定义在调用之后，那么编译器会为被调用的函数的函数做一些假设。如果假设错误，则程序无法正常工作。
说明：在调用前声明（declare）每个函数，函数声明是编译器对函数进行概要浏览，而函数的完整定义稍后再出现。

函数原型（function prototype）：c中将这种函数声明称为函数原型。原型为如何调用函数提供了一个完整的描述：提供了多少实际参数，这些参数应该是什么类型，以及返回的结果是什么类型。
行参规则：可以不写形式参数的名字，只要显示类型就可以，float average(float float)，但不建议，为了代码的可阅读性和可维护性。

语法：返回类型 函数名（形式参数）;
注意：函数的声明必须和函数的定义一致。

9.3 实际参数

分类 说明
形式参数(parameter) 出现在函数定义中，它们以假名字来表示函数调用时提供的值
实际参数(argument) 出现在函数调用中的表达式

通过值传递：调用函数时，计算出每个实际参数的值并且把它赋值给相应的形式参数。

特点：在函数的执行过程中，对形式参数的改变不会影响实际参数的值。

9.3.1 实际参数的转换

说明：c语言允许在实际参数的类型和形式参数的类型不匹配的情况下进行函数调用。

实参转换规则

编译器在调用前是否遇到原型 转换方式
是 实参的值被隐式转换成相应形式参数的类型。
否 编译器执行默认的实际参数提升

默认的实际参数提升

  1. 把float型的实际参数转换成double类型
  2. 执行整数的提升（即把char型和short型的实际参数转换成int型）
    注意：默认的实际参数提升不总会获得期望的效果
    技巧：始终在调用函数前声明函数非常必要。
1
2
3
4
5
6
7
int main(){
	int i;
	printf("Enter number to be squard:");
	scanf("%d", &i);
	//把变量i强制转换为正确的类型的方法
	printf("The answer if %g\n", square((double)i));
}

9.3.2 数组型实际参数

语法：数组类型 数组实参名[数组长度]
特点：

  • 其中数组长度通常省略不写。即便写了在函数中仍然无法判断数组的长度。
  • 多维数组形式参数只能忽略第一位的长度

获取实参数组长度：c语言没有提供任何简便的方法来确定传递给它的数组的长度。但是如果函数需要，必须把长度作为额外的实际参数提供给函数。
注意：在函数内部通过sizeof(a) / sizeof(a[0])的方式并不能正确计算出传递进来的数组的长度。
技巧：通过传递比数组实际长度小的整数参数，来部分操作数组。
延伸：不能传递令人困扰的具有任意列数的多维数组。幸运的是，我们经常可以通过使用指针数组的方式处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define LEN 100

/*函数原型*/
int sun_array(int a[], int n);//如果愿意可以省略形式参数的名字

int main(){
	int b[LEN], total;
	total = sun_array(b, LEN);//在数组名传递给函数时，不要在数组名的后边放置方括号
}

/**
* params{int Array} a 数组
* params{int} n 数组长度
*/
int sun_array(int a[], int n){
	int i, sun = 0;
	for(i = 0; i < n; i++){
		sun += a[i];
	}
	return sum;
}

9.4 return语句

return语句：return 表达式;
隐式转换：如果return语句中表达式的类型和函数的返回类型不匹配，那么系统将会把表达式的类型隐式转换为返回类型
立即返回：在返回类型为void的函数中可以使用return;，会导致函数立即返回，后面不能包含表达式

void和非void

返回值类型是否为void 是否必须return 说明
否 是 必须使用return 表达式返回值，否则某些编译器会报错
是 否 return并不是必须的，因为在执行最后一条语句后函数将会自动跳转。 
1
2
3
4
void print_pun(void){
	printf("To c, or not to C :that is the qyestion.\n")
	return;/*可以省略*/
}

9.5 程序终止

状态码：即main函数的返回值，默认为int类型；或者exit函数的实参。
状态码用途：在某些操作系统中程序终止时可以检测到状态码。

状态 状态码
正常终止 0
异常终止 非0

技巧：即使不打算用状态码，确信每个c程序都返回状态码也是一个很好的实践，因为某些运行程序的人可能稍后再决定测试状态码。

exit函数

功能：终止程序，相当于在main函数中使用return。
实参：传递给exit函数的实际参数和main函数的返回值具有相同的含义，两者都说明程序终止时的状态。
所在库：<stdlib.h>
相关宏定义：EXIT_SUCCESS和EXIT_FAILURE,值由实现定义，典型的值是0和1
区别于return：return和exit都可以在任何函数中调用，但return只有在main函数中调用才会终止程序；exit在任何函数中调用都会终止程序。
技巧：一些程序员专门使用exit函数以便于模式匹配程序可以很容易地定位程序中全部的退出点。

1
exit(EXIT_SUCCESS);

9.6 递归函数

说明：如果函数调用它本身，那么此函数就是递归的（recursice）。
技巧：为了防止无限递归，所有递归函数都需要某些类型的终止条件。
注意：c语言允许递归，但大多数c程序员并不经常使用递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 计算n的阶乘
*/
int face(int n){
	if(n <= 1){
		return 1;
	}else{
		return n * fact(n-1);
	}
}

/**
* 计算x^n
*/
int power(int x, int n){
	return n == 0 ? 1 : x * power(x, n - 1);
}

9.6.1 快速排序算法

分治法(divide-and-conquer)：把一个大问题划分成多个较小的问题，然后采用相同的算法分别解决这些小问题。比如排序算法。
算法操作：

  1. 选择数组元素e（作为“分割元素”），然后重新排列数组使得元素从1一直到i-1都是小雨或等于元素e的，元素i包含e，而元素从i-1一直到n都是大于或等于e的。
  2. 通过递归地采用快速排序算法，对从1到i-1的元素进行排序。
  3. 通过递归地采用快速排序方法，对从i+1到n的元素进行排序。

自己实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * Sorts an array of integers using Quicksort algorthm
 */
#include <stdio.h>

 #define N 12

 void quicksort(int a[], int low, int high);
 void printArr(int a[], int flag);

 int main(){
 	int a[N] = {5,4,7,8,3,0,7,1,9,2,0,6};
 			  
 	quicksort(a, 0, N-1);
 	printArr(a, 3);
 }

/**
 * 打印数组
 * @param {int} a 需要打印的数组
 * @param {int} flag 表示打印时排序处在的状态
 */
void printArr(int a[], int flag){
	printf("%d\n", flag);
	for(int i = 0; i < N; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
}
/**
 * 自己实现的快排程序：快速排序
 * @param {int} a[] 被排序的数组
 * @param {int} low 起点
 * @param {int} high 终点
 */
 void myquicksort(int a[], int low, int high){
 	printf("%d****%d\n", low, high);
 	if(low >= high){
 		return ;
 	}else{
 		int middleValue = a[low];
 		int emptyPoint = low;
 		int newLow = low, 
 			newHigh = high;
 		
 		/**
 		 * 只要low指针和high指针没有最后相遇，就交替往中间靠拢。并在在这个过程中完成位置的交换。
 		 * 原理是：有点像拆东墙补西墙，把中间数字两边的数字看作东墙和西墙的话，
 		 * 其实就是在东墙上找西墙上的砖补到西墙上，东墙被拿走砖的位置且只能是这个位置需要西墙去补。一来二去就完成了砖的交换过程。
 		 */
 		while(newLow < newHigh){
 			if(newLow == emptyPoint){
 				//待定的位置为低位：高位指针向左移动寻找比中间值小的数
 				while(a[newHigh] >= middleValue){
 					if(newHigh > newLow){
 						newHigh--;	
 					}else{
 						goto done;
 					}
 				}
 				a[emptyPoint] = a[newHigh];
 				emptyPoint = newHigh;
 			}else{
 				//待定的位置为高位：低位指针向右移动寻找比中间值大的数
 				while(a[newLow] <= middleValue){
 					if(newHigh > newLow){
 						newLow++;
 					}else{
 						goto done;
 					}
 				}
 				a[emptyPoint] = a[newLow];
 				emptyPoint = newLow;
 			}
 			printArr(a, 1);
 		}
 		//标记
 		done:
 		a[emptyPoint] = middleValue;
 		printArr(a, 0);
 		if(newLow > low){
 			quicksort(a, low, newLow - 1);	
 		}
 		if(newHigh < high){
 			quicksort(a, newHigh + 1, high);	
 		}
 	}	
 }

9.6.2 程序：快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Sorts an array of intergers using Quicksort algorithm
 */
#include <stdio.h>
 #define N 10
 /*声明函数*/

 void quicksort(int a[], int low, int high);
 int split(int a[], int low, int high);

 int main(){
 	int a[N], i;

 	/*输入需要排队的数组*/
 	printf("Enter %d numbers to be sorted :", N);
 	for(i = 0; i < N; i++){
 		scanf("%d", &a[i]);
 	}

 	/*调用排序函数进行排序*/
 	quicksort(a, 0, N - 1);

 	/*打印排序好的数组*/
 	printf("In sorted order:");
 	for(i = 0; i < N; i++){
 		printf("%d ", a[i]);
 	}
 }

/**
 * 快排程序
 * @param {Array} a 数组
 * @param {int} low 开始下标 
 * @param {int} high 结束下标
 */
 void quicksort(int a[], int low, high){
 	int middle;
 	if(low >= high){
 		return;
 	}
 	//获得分段的中间位置
 	middle = split(a, low, high);
 	quicksort(a, low, middle -1);
 	quicksort(a, middle + 1, high);
 }

 int split(int a[], int low, int high){
 	int part_element = a[low];
 	for(;;){
 		/*high指针向左移动寻找比part_element小的数，直到找到或low和high指针重合*/
 		while(low < high && part_element <= a[high]){
 			high--;
 		}
 		//如果重合了，说明没有找到
 		if(low >= high){
 			break;
 		}
 		//如果找到了，将找到的比中间值小的数放到当前low指针指向的位置，并将指针向右移动
 		a[low++] = a[high];

 		/*low指针向右移动，寻找比part_element大的数，直到找到一个或low和high重合*/
 		while(low < high && a[low] <= part_element){
 			low++;
 		}
 		//重合了就停止循环
 		if(low >= high){
 			break;
 		}
 		//如果没重合，就讲找到的数移动到high指针指向的位置，并将high的指针向左移动一下
 		a[high--] = a[low];
 		return high;
 	}
 }

9.6.3 改进

  1. 改进分割算法
    上面介绍的方法不是最有效的。我们不再选择数组中的第一个元素作为分割元素，较好的方法是取第一个元素、中间元素和最后一个元素的中间值。分割过程本身也可以加速。特别是，在两个while循环中避免测试low<high是可能的。

  2. 采用不同的方法进行小数组排序

  3. 使得快速排序非递归
    虽然快速排序本质上是使用递归算法，并且递归格式的快速排序是最容易理解的，但是实际上若去掉递归会更有效率。